home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 412_01 / src / unisear / search.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1994-03-29  |  3.2 KB  |  135 lines
  1. #include <new.h>
  2. #include "search.h"
  3.  
  4. /*                      SEARCH_
  5.  
  6.     The constructor puts the start node on open, saves the goal node
  7.     and sets the number of operators to the specified value.
  8.  
  9. */
  10.  
  11. SEARCH_::SEARCH_(NODE_ *start, NODE_ *goal, int op)
  12. {
  13.     open.addtohead(*start);    // put the start node on open
  14.     num_op = op;
  15.     goalnode = goal;
  16. }
  17.  
  18.  
  19.  
  20. /*                      ~SEARCH_
  21.  
  22.     The destructor only deallocates the memory occupied by the goalnode.
  23.  
  24. */
  25.  
  26. SEARCH_::~SEARCH_()
  27. {
  28.     delete(goalnode);
  29. }
  30.  
  31.  
  32.  
  33. /*                    PRINT_SOL
  34.  
  35.     Prints the solution by tracing back through the parent *'s. So, we
  36.     recurse a little (well...)
  37.  
  38. */
  39.  
  40. void SEARCH_::print_sol(NODE_ *sol) const
  41. {
  42.     if (!sol)
  43.         return;
  44.     print_sol(sol->getparent());
  45.     sol->display();
  46. }
  47.  
  48.  
  49.  
  50. /*                   GENERATE
  51.  
  52.     Starts the search process by calling solve() and prints the
  53.     solution if found by calling print_sol().
  54.  
  55. */
  56.  
  57. #ifdef MSC
  58.     extern int no_mem(size_t);
  59. #else
  60.     extern void no_mem();
  61. #endif
  62.  
  63. void SEARCH_::generate()
  64. {
  65.     NODE_
  66.         *sol;
  67.  
  68. #ifdef MSC
  69.     _set_new_handler(no_mem);
  70. #else
  71.     set_new_handler(no_mem);
  72. #endif
  73.  
  74.     if (!(sol = solve()))
  75.     {
  76.         puts("No solution found");
  77.         return;
  78.     }
  79.  
  80.     print_sol(sol);
  81. }
  82.  
  83.  
  84.  
  85. /*                      SOLVE
  86.  
  87.     This routines implements the actual search engine. It takes the first
  88.     node from OPEN, if OPEN is empty the search process fails. If not, the
  89.     node is moved to CLOSED. Next, the node's successors are generated by
  90.     calling NODE_::expand(). Then, every successor is made to point
  91.     back to its parent, so that the solution path may be traced back once
  92.     the solution is found. Each successor is passed to add() for further
  93.     processing, if add() returns 0 this means that the the successor
  94.     already was on OPEN and consequently it can be thrown away, i.e. it gets
  95.     deallocated.
  96.  
  97.     Solve() returns the goal node if found and NULL otherwise.
  98. */
  99.  
  100. NODE_ *SEARCH_::solve()
  101. {
  102.     NODE_
  103.         *father,
  104.         *child,
  105.     *next,
  106.         *goal = NULL;
  107.  
  108.     while((father = (NODE_ *) open.gethead()) != NULL)
  109.     {                                          // get first node from open
  110.         open.remove_head();
  111.         closed.addtohead(*father);             // put it on closed
  112.  
  113.         child = father->expand(num_op);        // expand the node 
  114.         while (child)
  115.         {
  116.             child->setparent(father);          // so I can remember my daddie
  117.  
  118.             if (goalnode->equal(*child))       // found a goal node
  119.                 goal = (goal == NULL || goal->eval(*child)) < 0 ?
  120.                        goal : child;
  121. /* We don't stop immediately after finding the goal node, because we may be
  122.    looking for the best or cheapest path and a better/cheaper goal node may
  123.    still be ahead in the list */
  124.             next = child->getnext();
  125.             if (!add(child))
  126.                 delete(child);               // child aready in graph: kill it!
  127.             child = next;        
  128.         }
  129.         if (goal)
  130.             return(goal);
  131.     }
  132.     return(NULL);
  133. }
  134.  
  135.